package sort;

import java.util.Arrays;

/**
 * 描述:
 *
 * @author
 * @created 2021/12/30 9:24
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        /*增量gap，逐步缩小增量*/
        /*gap是步长，每次步长为二分之一*/
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            /*从第gap个元素，逐个对其所在的组进行直接插入排序*/
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                while (j - gap >= 0 && arr[j] < arr[j - gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                    j -= gap;
                }
            }
        }
    }

}
